﻿public class Solution {
    public int StrStr(string haystack, string needle)
    {
        // 构造next数组
        int[] next = GetNext(needle);
        // 查找子串
        int j = 0;
        for (int i = 0; i < haystack.Length; i++)
        {
            while (j > 0 && haystack[i] != needle[j])
            {
                j = next[j - 1];
            }

            if (haystack[i] == needle[j])
            {
                j++;
            }
            
            // 找到子串
            if (j == needle.Length)
            {
                return i - j + 1;
            }
        }
        return -1;
    }

    private int[] GetNext(string needle)
    {
        int[] next = new int[needle.Length];
        int j = 0;
        next[0] = j;
        
        // 填充next数组
        for (int i = 1; i < needle.Length; i++)
        {
            while (j > 0 && needle[i] != needle[j])
            {
                j = next[j - 1];
            }

            if (needle[i] == needle[j])
            {
                j++;
            }

            next[i] = j;
        }

        return next;
    }

    public static void Main(string[] args)
    {
        string haystack = "aabaabaafa", needle = "aabaaf";
        Solution solution = new Solution();
        int res = solution.StrStr(haystack, needle);
        Console.WriteLine(res);
    }
}